package algorithm_primary.studyMySelf.五百六和为K的子数组;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 衡孟浩
 * @date 2023/8/29 14:07
 * <p>
 * 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [1,1,1], k = 2
 * 输出：2
 * 示例 2：
 * <p>
 * 输入：nums = [1,2,3], k = 3
 * 输出：2
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= nums.length <= 2 * 104
 * -1000 <= nums[i] <= 1000
 * -107 <= k <= 107
 */
public class 五百六 {
    public static void main(String[] args) {
        //int[] nums = {3, 2, 4, 1, 12, 14, 15, 16, 3, 5, 6, 1,1, 2, 2};
        int[] nums = {1,-1,0};
        int k = 0;
        int i = subarraySum(nums, k);
        System.out.println("i = " + i);
    }


    public static int subarraySum(int[] nums, int k) {
        int length = nums.length;
        // 存放每一次 各个元素相加的值
        Map<Integer, Integer> map = new HashMap<>(length);
        int sum = 0, result = 0;
        // key: 代表如果k和某个和相减为0 那么必有这个子数组相加 等于 k的  value: 默认出现一次
        map.put(0, 1);
        for (Integer num : nums) {
            // 相加
            sum += num;
            int key = sum - k;
            // 如果不存在这个key  代表当前遍历到值前边没有子数组为k的  所以让result加 0 等于没操作
            // 如果存在 那么直接加前边出现的次数
            result += map.getOrDefault(key, 0);
            // 默认为1次  如果之前就有这个次数，那么直接在原有基础上+1让下次加
            map.put(sum, map.containsKey(sum) ? map.get(sum) + 1 : 1);
        }
        return result;
    }
}
